//
// Created by Administrator on 2024/2/24.
// 讲解: https://www.bilibili.com/video/BV11g411c7Jm/
//

#include <iostream>
#include <vector>
#include "arrUtil.h"

using namespace std;

vector<int> merge(vector<int> l, vector<int> r)
{
    vector<int> t;
    int li=0,ri=0;
    while(li<l.size() && ri<r.size())
    {
        if(l[li]<=r[ri])
        {
            t.push_back(l[li]);
            li++;
        }else{
            t.push_back(r[ri]);
            ri++;
        }
    }
    for(;li<l.size();li++) t.push_back(l[li]);
    for(;ri<r.size();ri++) t.push_back(r[ri]);
    return t;
}

vector<int> mergeSort(vector<int> v)
{
    if (v.size()>1)
    {
        vector<int> l,r;
        int m=v.size()/2;
        for (int i = 0; i < m; ++i)
            l.push_back(v[i]);
        for (int i = m; i < v.size(); ++i)
            r.push_back(v[i]);
        return merge(mergeSort(l),mergeSort(r));
    }
    return v;
}
int main()
{
//    vector<int> a={3,6,8,9};
//    vector<int> b={1,2,5,7,10,20};
//    vector<int> ret = merge(a,b);
//    printVector(ret);
    vector<int> b={1,2,5,7,23,6,8,9,10,20};
    randVector(b,1000);
    vector<int> ans = mergeSort(b);
//    printVector(ans);
    cout<<checkSortVector(ans);
    return 0;
}